class HashTable<T = any> {
    // 创建一个数组，用来存放链表地址中的链(数组),这里string是键的类型，T是value的类型，其是一个元组类型，然后其放在一个数组里面，再放入另一个数组里面
    // 数组里面放数组，然后数组里面的每一项都是元组
    private storage: [string,T][][] = [];
    // 定义数组的长度，count/length 为哪个什么因子，大于0.75提醒扩容(增加数组长度)
    private length: number = 7;
    // 记录已经存在的元素的个数
    private count: number = 0;

    private hashFunc(key: string, max:number):number{ 
        let hashCode = 0;
        const length = key.length;
        for (let i = 0; i < length; i++) {
            // 公式
            hashCode = 31 * hashCode + key.charCodeAt(i);
        }
        // 计算出索引值
        const index = hashCode % max;
    
        return index
    }
    //插入-修改
    put(key:string,value:T){
        // 1.根据key获取数组的索引值
        const index = this.hashFunc(key,this.length);

        // 2.根据索引取出对应的数组
        let bucket = this.storage[index];

        // 3.判断bucket是否有值
        if(!bucket){
            bucket = [];
            this.storage[index] = bucket;
        }
        // 记录是否发生覆盖
        let isUpdate = false;
        // 4.确定已经有一个数组，但是数组里面是否已存在key是不确定的
        for(let i = 0; i < bucket.length; i++){
            const tuple = bucket[i]
            const tupleKey = tuple[0];//key
            //tuple[1]是value
            if(tupleKey === key){
                //修改操作
                tuple[1]= value;
                isUpdate = true
            }
        }
        // 表示没有发生过覆盖
        if(!isUpdate){
            bucket.push([key,value]);
            this.count++;
        }
    }
    
    // 获取值
    get(key: string) : T | undefined {
        // 1、根据key 获取索引值index
        const index = this.hashFunc(key,this.length)

        // 2、获取bucket(桶)
        const bucket = this.storage[index]
        // 如果桶不存在，直接返回undefined
        if(!bucket) return undefined;

        //3、对桶进行遍历
        for (let i = 0; i < bucket.length; i++){
            const tuple = bucket[i];
            let tupleKey = tuple[0];
            let tupleValue = tuple[1];
            if(tupleKey === key){
                return tupleValue
            }
            return undefined
        }
    }
}

const hashTable = new HashTable();

hashTable.put('aaa',100);
hashTable.put('aaa',200);
hashTable.put('bbb',300);

console.log(hashTable.get('aaa'));

console.log(hashTable.get('bbb'));

console.log(hashTable.get('abc'));

console.log(hashTable.get('ddd'));

export default {}


// 原组类型放在数组里面再放入数组里面
// let tuple:[number,number][][] = [[[111,2222]]]